package gold.gold01;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

/**
 * 简单， 看起来另外维护一个最小栈
 * 34, 82
 * pop出最小值的时候, 扫描一下链表获得新的最小值
 * 注意第二种解法, 明明有Stack类, 用什么ArrayList?学一下Stack。
 */
public class S0302栈的最小值 {
    private ArrayList<Integer> stack = new ArrayList<>();
    // min[0]为最小值, min[1]为最小值的位置, -1表示还未添加值。
    private int[] min = new int[]{0, -1};
    public S0302栈的最小值() {

    }

    public void push(int x) {
        if(min[1] == -1){
            min[0] = x;
            min[1] = 0;
        }
        stack.add(x);
        if(x < min[0]){
            min[0] = x;
            min[1] = stack.size() - 1;
        }
    }

    public void pop() {
        if(stack.size() == 0) return;
        stack.remove(stack.size() - 1);
        if(stack.size() == 0){
            min[0] = 0;
            min[1] = -1;
        }
        if(stack.size() == min[1]){
            min[0] = Collections.min(stack);
            min[1] = stack.indexOf(min[0]);
        }
    }

    public int top() {
        return stack.size() == 0? 0: stack.get(stack.size() - 1);
    }

    public int getMin() {
        return min[0];
    }
}

/**
 * 如果面试官问, 想要第二小, 第三小之类的值, 那么上面的解法没有办法解决。
 * 需要使用两个栈, 一个顺序栈, 一个有序栈。
 */
class MinStack {
    private Stack<Integer> data_stack = new Stack<>();
    private Stack<Integer> min_stack = new Stack<>();

    public MinStack() {

    }
    // 如果新push的值小于本来的最小值, 那么小值栈就把栈顶的值再push一次
    // 即两个栈等长, 第一个就正常栈, 第二个和第一个等长, 但是存的是每个位置上的当前最小值
    public void push(int x) {
        data_stack.push(x);
        if (min_stack.empty() || x < min_stack.peek()) {
            min_stack.push(x);
        } else {
            min_stack.push(min_stack.peek());
        }
    }

    public void pop() {
        data_stack.pop();
        min_stack.pop();
    }

    public int top() {
        return data_stack.peek();
    }

    public int getMin() {
        return min_stack.peek();
    }
}
